Steganographic and watermarking techniques have been used to hide ancillary information in many different types of media. Steganographic techniques are generally used when the purpose is to conduct some type of secret communication and stealth is critical to prevent the interception of the hidden message. Watermarking techniques are more appropriate where the primary concern is to protect the hidden information, the watermark, from damage or removal.
In steganography a classic model is known as the “prisoners' problem”. One example of the prisoners' problem is a scenario where Alice and Bob are two prisoners sent to different cells. Any communication between them must go through a warden Wendy. Because the warden wants to ensure that they are not developing an escape plan, she will not allow encrypted messages or any other suspicious communication. Therefore, Alice and Bob must set up a subliminal channel to communicate their escape plan invisibly.
Based on this model, steganography works as follows. When Alice wants to send a secret message to Bob she first selects a cover-object c. The cover-object is some harmless message which will not raise suspicion. She then embeds the secret message m in the cover-object to produce the stego-objects. The stego-object must be created in such a way that Wendy, knowing only the seemingly harmless message s, will not be able to detect the presence of a secret in the cover-object c. Alice then transmits the message s over an insecure channel to Bob. Once received, Bob is able to decode the message m since he knows the embedding method and their shared secret key.
Steganography is useful in many applications, such as the prevention of piracy of media. When using still images, video, or audio as the cover media we are able to leverage limitations in the human visual and auditory systems. This has led to a plethora of research on digital steganography and watermarking. Unfortunately, when the cover medium is an executable program we are far more restricted as to the type of transformations we can apply. These restrictions have resulted in fewer techniques, most of which suffer from inadequate data rates and/or poor resistance to attack.
In contrast to image and sound steganography very little attention has been paid to code steganography. Most of the research directed at hiding information in executables has focused on providing piracy protection and thus has taken the form of software watermarking. A number of software watermarking techniques have been developed and proposed. Some software watermarking algorithms embed the watermark through an extension to a method's control flow graph. The watermark is encoded in a subgraph which is incorporated in the original graph. In other techniques, the instruction frequencies of the original program are modified to embed the watermark. A dynamic watermarking algorithm has been proposed which embeds the watermark in the structure of the graph, built on the heap at runtime, as the program executes on a particular input. Other proposed techniques are path-based and rely on the dynamic branching behavior of the program. To embed the watermark the sequence of branches taken and not taken on a particular input are modified. An abstract interpretation framework may also be used to embed a watermark in the values assigned to integer local variables during program execution. Other techniques leverage the ability to execute blocks of code on different threads. The watermark is encoded in the choice of blocks executed on the same thread. Also, a branch function may be used which generates the watermark as the program executes.
In addition to software watermarking, other techniques are aimed directly at code steganography. For example one technique draws on the inherent redundancy in the instruction set to encode a message by noting that several instructions can be expressed in more than one way. For example, adding a value x to a register can be replaced with subtracting −x from the register. By creating sets of functionally equivalent instructions, message bits can be encoded in the machine code. Two improvements on the equivalent instruction substitution technique have been proposed using alternative encoding methods. The first technique is based on the ordering of basic blocks. The chain of basic blocks is selected based on the bits to be encoded. The second technique operates on a finer granularity and relies on the ordering of the instructions within a basic block. One recent code steganography technique is suggested not as a method for transferring secret messages, but as a way to provide additional information to the processor. The information encoding is accomplished by modifying operand bits in the instruction. To ensure proper execution a look-up table is stored in the program header.
Each of the above techniques has certain disadvantages such as inadequate data rates and poor resistance to attack.
Accordingly, there is a need for methods and systems for providing hidden messages in executable programs which have acceptable data rates and are very resistant to attack.